﻿#pragma once
#include "FormatedUtil.h"
#include "Index.h"

class IMaxValueInGrid
{
public:
	/**
	 * 礼物的最大价值.
	 * @see 矩阵的最小路径和.
	 * https://www.nowcoder.com/practice/2237b401eb9347d282310fc1c3adb134?tpId=265&tqId=39288&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D13&difficulty=undefined&judgeStatus=undefined&tags=&title=
	 */
	virtual int MaxValueInGrid(std::vector<std::vector<int>>& grid) = 0;
};

class MaxValueInGridSolution
{
public:
	class DP:public IMaxValueInGrid
	{
	public:
		/**
		 * 动态规划解法
		 * 时间O(n) 空间:O(grid.colSize)
		 */
		int MaxValueInGrid(std::vector<std::vector<int>>& grid) override
		{
			const int rowSize = grid.size();
			const int colSize = grid.front().size();
			if (rowSize <= 0 || colSize <= 0)
				return 0;

			//在grid中每两行交替迭代的dp,dp[i][j]表示到达grid[i][j]上时礼物的最大值
			std::vector<int> valDp[2] = {
				std::vector<int>(colSize,0),std::vector<int>(colSize,0) };

			//逐行
			for (int i = 0; i < rowSize; ++i)
			{
				std::vector<int>& curDp = valDp[i % 2];
				std::vector<int>& lastDp = valDp[(i + 1) % 2];
				//逐列
				for (int j = 0; j < colSize; ++j)
				{
					if (j > 0)
						curDp[j] = std::max<int>({ curDp[j - 1],lastDp[j] }) + grid[i][j];
					else
						curDp[j] = lastDp[j] + grid[i][j];
				}
			}

			return valDp[(rowSize - 1) % 2][colSize - 1];
		}
	};
};


#ifdef DEV_TEST
#include <gtest/gtest.h>
class MaxValueInGridTest:public SolutionTestor<IMaxValueInGrid>
{
protected:
	void LoadSolutions(std::vector<IMaxValueInGrid*>& solutions) override
	{
		solutions = {
			new MaxValueInGridSolution::DP,
		};
	}
};
TEST_F(MaxValueInGridTest, MaxValueInGrid)
{
	TestForSolutions([](IMaxValueInGrid* solution)
	{
		std::map<String, int> testSamples;
		testSamples["[[1,3,1],[1,5,1],[4,2,1]]"] = 12;
		testSamples["[[]]"] = 0;
		testSamples["[[],[]]"] = 0;
		testSamples["[[1,2,3,4]]"] = 10;
		testSamples["[[1,1,1,1],[1,1,1,1]]"] = 5;

		for (auto kvp : testSamples)
		{
			const auto& input = kvp.first;
			const auto& expectedResult = kvp.second;

			std::vector<std::vector<int>> grid;
			FormatedUtil::parseFormated(grid, input);
			EXPECT_EQ(solution->MaxValueInGrid(grid), expectedResult);
		}
	});
}
#endif
